Modern software programs include many instructions that are executed multiple times each time the program is executed. Typically, large programs have logical “regions” of instructions, each of which may be executed many times. When a region is one that is executed more than once, and the results produced by the region are the same for more than one execution, the region is a candidate for “reuse.” The term “reuse” refers to the reusing of results from a previous execution of the region.
For example, a reuse region could be a region of software instructions that, when executed, read a first set of registers and modify a second set of registers. The data values in the first set of registers are the “inputs” to the reuse region, and the data values deposited into the second set of registers are the “results” of the reuse region. A buffer holding inputs and results can be maintained for the region. An entry in the buffer is termed an “instance.” When the region is encountered during the execution of the program, the buffer is consulted and if an instance with matching input values is found, the results can be used without having to execute the software instructions in the reuse region. When reusing the results is faster than executing the software instructions in the region, performance improves.
The example of the previous paragraph works well when the results are a function of nothing but the input values. When the results are a function of more than the input values, reuse is more complicated. For example, if a memory load instruction occurs in the reuse region, the results can be a function of the input values as previously described, and can also be a function of the data value loaded from the memory. If the memory load instruction accesses a memory location that is changed by a memory update instruction outside the region, then the region is said to be “aliased.”
Aliased regions present a problem for reuse. Even when a matching instance exists in the reuse buffer, the reuse instance may not be usable because the aliased memory load instruction may read a different value that causes the correct results to differ from the results in the instance. Therefore, it is important to identify reuse instances that cannot be reused. One approach is to use an “invalidate” instruction that is placed after memory update instructions capable of writing to the same location that the aliased load instruction accesses. Typically, the invalidation instruction includes a parameter identifying a reuse region. When the invalidation instruction is executed, reuse instances of the reuse region are invalidated.
However, it can be difficult and time consuming to find all of the memory update instructions that may update the aliased address and to insert an invalidation instruction after each found update instruction. Furthermore, even if all of the appropriate instructions can be found, this approach is conservative in part because the memory update instruction may update an address other than the aliased address, but the invalidate instruction will invalidate the region nonetheless.
Therefore, there is a need in the art for an alternate method and apparatus for invalidating instances of aliased reuse regions.